3.1 Three in One:

Describe how you could use a single array to implement three stacks.



In [ ]:

3.2 Stack Min:

How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in 0(1) time.



In [28]:

    
import sys
capacity = 30

class Stack():
    def __init__(self, capacity):
        self.last = -1
        self.capacity = capacity
        self.mem = [(0, 0) for _ in range(capacity)]

    def push(self, value):
        if self.last < capacity - 1:
            min_val = min(self.min(), value)
            self.last += 1
            self.mem[self.last] = (value, min_val) 

    def min(self):
        if self.last == -1:
            return sys.maxsize
        else:
            value, min_val = self.mem[self.last]
            
            return min_val
                                   
    def pop(self):
        if self.last == -1:
            value = None
        else:
            value, _ = self.mem[self.last]
            self.last -= 1
        return value
    
    def __str__(self):
        out_ch_list = [str(self.mem[i])for i in range(self.last + 1)]
        return ",".join(out_ch_list)
    
stack = Stack(capacity)
print(stack)
print(stack.min())
stack.push(19)
print(stack)
print(stack.min())
stack.push(10)
print(stack)
print(stack.min())
stack.push(1)
print(stack)
print(stack.min())
stack.pop()
print(stack)
print(stack.min())
stack.pop()
print(stack)
print(stack.min())









    



9223372036854775807
(19, 19)
19
(19, 19),(10, 10)
10
(19, 19),(10, 10),(1, 1)
1
(19, 19),(10, 10)
10
(19, 19)
19



In [ ]: